A content addressable memory (CAM) is a memory device that accelerates any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. CAMs provide benefits over other memory search algorithms by simultaneously comparing the desired information (i.e., data being stored within a given memory location) against the entire list of pre-stored entries. As a result of their unique searching algorithm, CAM devices are frequently employed in network equipment, particularly routers and switches, computer systems and other devices that require rapid content searching.
In order to perform a memory search in the above-identified manner, CAMs are organized differently than other memory devices (e.g., random access memory (RAM), dynamic RAM (DRAM), etc.). For example, data is stored in a RAM in a particular location, called an address. During a memory access, the user supplies an address and reads into or gets back the data at the specified address.
In a CAM, however, data is stored in locations in a somewhat random fashion. The locations can be selected bib an address bus, or the data can be written into the first empty memory location. Every location has a pair of status bits that keep track of whether the location is storing valid information in it or is empty and available for writing.
Once information is stored in a memory location, it is found by comparing every bit in memory with data placed in a match detection circuit. When the content stored in the CAM memory location does not match the data placed in the match detection circuit, the CAM device returns a no match indication. When the content stored in the CAM memory location matches the data placed in the match detection circuit, the CAM device returns a match indication. In addition, the CAM may return the identification of the address location in which the desired data is stored. Thus, with a CAM, the user supplies the data and gets back the address if there is a match found in memoir.
Locally, CAMs perform an exclusive-NOR (XNOR) function, so that a match is indicated only if both the stored bit and the corresponding input bit are the same state. CAMs are designed so that any number of stored bits may be simultaneously detected for a match with the input bits in the match detection circuit. One way in which this is achieved is by coupling a plurality of storage devices and logic circuits to a common Matchline, as depicted in FIG. 1.
Turning to FIG. 1, a schematic diagram of a conventional match detection circuit 100 is depicted. A first source/drain terminal of a precharge transistor 102 is coupled to a positive voltage source (e.g., VDD). The gate of transistor 102 is coupled to a signal line 138 for receiving a Precharge signal. A second source/drain terminal of transistor 102 is coupled to a Matchline 140 for precharging the Matchline 140 to a predetermined voltage level (e.g., VDD).
Respective outputs Q0, Q1, Qn−1 of storage elements 104, 114, 124, which are to be respectively compared with the input bits B0, B1, Bn−1 are respectively coupled to gates of transistors 106, 116 and 126. First respective source/drain terminals of transistors 106, 116 and 126 are coupled to the Matchline 140.
Second respective source/drain terminals of transistors 106, 116 and 126 are respectively coupled to transistors 110, 120 and 130. Second respective source/drain terminals of transistors 110, 120 and 130 are coupled to ground. The gates of transistors 110, 120 and 130 are respectively coupled to complements B0′, B1′ and Bn−1′ of the respective input bits.
Further, the respective complements of the outputs Q0′, Q1′ and Qn−1′ of the storage elements 104, 114 and 124 are respectively coupled to gates of transistors 108, 118 and 128. First respective source/drain terminals of transistors 108, 118 and 128 are coupled to the Matchline 140. Second source/drain terminals of transistors 108, 118 and 128 are respectively coupled to first source/drain terminals of transistors 112, 122 and 132. Second respective source/drain terminals of transistors 112, 122 and 132 are coupled to ground. The gates of transistors 112, 122 and 132 are respectively coupled to the input bits B0, B1 and Bn−1 to be respectively compared with the complements Q0′, Q1′ and Qn−1′ of the stored bits being stored in storage elements 104, 114 and 124.
Also coupled to the Matchline 140 is a buffer 136 for buffering the Matchline 140 voltage and for outputting the Match signal. A Match signal of logic HIGH (e.g., VDD) represents that an exact match was detected between the input bits B0, B1, Bn−1 and the stored bits Q0, Q1, Qn−1. A Match signal of logic LOW (e.g., Ground) represents that at least one bit of the stored bits did not match its corresponding input bit causing the Matchline to be pulled to Ground. Capacitor 134 represent the parasitic capacitance of the Matchline 140 that is precharged to the initial predetermined value (e.g., VDD).
During operation of the FIG. 1 match detection circuit 100, the Precharge signal goes logic HIGH then logic LOW in order to precharge the Matchline 140 to VDD. The state of the stored bits Q0, Q1, Qn−1 stored by the respective storage elements 104, 114, 124 and their complements Q0′, Q1′, Qn−1′ are respectively coupled to the gates of p-type transistors 106, 116, 126, 108, 118, 128. Consequently, depending upon the states at their respective gates, the transistors 106, 116, 126, 108, 118, 128 may become active and conduct.
Similarly, the state of the input bits B0, B1, Bn−1 and their complements B0′, B1′, Bn−1′ are coupled to the gates of p-type transistors 112, 122, 132, 110, 120, 130. Consequently, depending upon the states at their respective gates, the transistors 112, 122, 132, 110, 120, 130 may become active and conduct.
When a match is detected, at least one transistor of each serially connected pair of transistors (e.g., 106 and 110, 108 and 112, etc.) is inactive and not conducting. Therefore, when the Matchline 140 remains logic HIGH, this signifies to the outside world that a match has been detected and potentially enables any other functions desired when a match is detected (e.g., provide the user with the address of the memory location where the match as found, forward the data to another location, etc.).
However, when a mismatch is detected, as is most often the case during a search for a particular bit pattern, at least one pair of serially connected transistors (e.g., 106 and 110) is active and conducting and the Matchline 140 is coupled to Ground. When the Matchline 140 is coupled to Ground, the Match signal goes logic LOW and signifies to the outside world that a mismatch has been detected in this particular series of storage elements 104, 114, 124.
In the above-identified search process, the searched data (i.e., the input bits) is simultaneously compared with every data word in the CAM in order to find a match between the stored data and the input data. Since the comparison operation is conducted simultaneously on the entire memory, and is typically repeated at a very high frequency, this operation consumes a significant amount of power.
Power dissipation, P, in complementary metal-oxide semiconductor (CMOS) circuits, such as that depicted in FIG. 1, is related to the magnitude of signal swing, V, the load capacitance C, and the frequency of operation F as P=C*F*V2. Since the magnitude of signal swing, V, for typical match detection circuits is from VDD to Ground, the power dissipated by the circuit is exceedingly high. Therefore, it is desirable to find a way to reduce power dissipation of CAM match detection circuits while maintaining the same levels of accuracy.